package class07



/*
	给定一个有序的正整数数组arr和一个正数aim，如果可以自由选择arr中的数字，
	想累加得到 1-aim 范围上所有的数，返回arr最少缺几个数
	【举例】
		arr = {1,2,3,7}, aim = 15
		想累加得到1-15范围上所有的数，arr还缺14这个数，所以返回1
		arr = {1,5,7}, aim = 15
		想累加得到 1-15 范围上所有的数，arr还缺2，4，所以返回2

	【算法流程】：
		前置条件：数组有序
		步骤：
			1. 初始化 range 为 0
			2. 遍历输入数组，数组从小到大，如果当前数大于 range + 1
			3. 补充一个数，将范围扩大到 range + arr[i]
			4. 循环，直到范围扩充到了 目标数字 aim
		分支：
			3.a
				3.a.1 遍历输入数组，数组从小到大，如果当前数小于 range + 1
				3.a.2 range 直接扩大到 range + arr[i]
				3.a.3 继续循环，直到范围扩充到了 目标数字 aim 退出循环
*/

func MinPatches(arr []int, aim int) int {
	var extendRange, patches int
	for i:=0; i<len(arr); i++ {
		for arr[i] > extendRange+1 {
			extendRange = extendRange*2 + 1
			patches++
			if extendRange >= aim {
				return patches
			}
		}

		extendRange = extendRange + arr[i]
		if extendRange >= aim {
			return patches
		}
	}
	// 如果遍历完数组，还是达不成目标
	for extendRange < aim {
		extendRange = extendRange*2 + 1
		patches++
	}
	return patches
}